package com.code.test.ali;


/**
 * https://leetcode.cn/problems/car-pooling/solutions/2546591/pin-che-by-leetcode-solution-scp6/
 * <p>
 * 举例
 * 考虑数组 a=[1,3,3,5,8]a=[1,3,3,5,8]a=[1,3,3,5,8]，对其中的相邻元素两两作差（右边减左边），得到数组 [2,0,2,3][2,0,2,3][2,0,2,3]。然后在开头补上 a[0]a[0]a[0]，得到差分数组
 * <p>
 * d=[1,2,0,2,3]d=[1,2,0,2,3]
 * d=[1,2,0,2,3]
 * 这有什么用呢？如果从左到右累加 ddd 中的元素，我们就「还原」回了 aaa 数组 [1,3,3,5,8][1,3,3,5,8][1,3,3,5,8]。这类似求导与积分的概念。
 * <p>
 * 这又有什么用呢？现在把连续子数组 a[1],a[2],a[3]a[1],a[2],a[3]a[1],a[2],a[3] 都加上 101010，得到 a′=[1,13,13,15,8]a'=[1,13,13,15,8]a
 * ′
 * =[1,13,13,15,8]。再次两两作差，并在开头补上 a′[0]a'[0]a
 * ′
 * [0]，得到差分数组
 * <p>
 * d′=[1,12,0,2,−7]d'=[1,12,0,2,-7]
 * d
 * ′
 * =[1,12,0,2,−7]
 * 对比 ddd 和 d′d'd
 * ′
 * ，可以发现只有 d[1]d[1]d[1] 和 d[4]d[4]d[4] 变化了，这意味着对 aaa 中连续子数组的操作，可以转变成对差分数组 ddd 中两个数的操作。
 * <p>
 * 定义和性质
 * 对于数组 aaa，定义其差分数组（difference array）为
 * <p>
 * d[i]={a[0],i=0a[i]−a[i−1],i≥1d[i] = \begin{cases} a[0],&i=0\\ a[i]-a[i-1],&i\ge 1 \end{cases}
 * d[i]={
 * a[0],
 * a[i]−a[i−1],
 * ​
 * <p>
 * i=0
 * i≥1
 * ​
 * <p>
 * 性质 1：从左到右累加 ddd 中的元素，可以得到数组 aaa。
 * <p>
 * 性质 2：如下两个操作是等价的。
 * <p>
 * 把 aaa 的子数组 a[i],a[i+1],⋯ ,a[j]a[i],a[i+1],\cdots,a[j]a[i],a[i+1],⋯,a[j] 都加上 xxx。
 * 把 d[i]d[i]d[i] 增加 xxx，把 d[j+1]d[j+1]d[j+1] 减少 xxx。
 * 利用性质 2，我们只需要 O(1)\mathcal{O}(1)O(1) 的时间就可以完成对 aaa 的子数组的操作。最后利用性质 1 从差分数组复原出数组 aaa。
 * <p>
 * 注：也可以这样理解，d[i]d[i]d[i] 表示把下标 ≥i\ge i≥i 的数都加上 d[i]d[i]d[i]。
 * <p>
 * 本题思路
 * 对于本题，设 a[i]a[i]a[i] 表示车行驶到位置 iii 时车上的人数。我们需要判断是否所有 a[i]a[i]a[i] 都不超过 capacity\textit{capacity}capacity。
 * <p>
 * trips[i]\textit{trips}[i]trips[i] 相当于把 aaa 中下标从 fromi\textit{from}_ifrom
 * i
 * ​
 * 到 toi−1\textit{to}_i-1to
 * i
 * ​
 * −1 的数都增加 numPassengersi\textit{numPassengers}_inumPassengers
 * i
 * ​
 * 。这正好可以用上面讲的差分数组解决。
 * <p>
 * 例如示例 1 对应的 ddd 数组，d[1]=2, d[5]=−2, d[3]=3, d[7]=−3d[1]=2,\ d[5]=-2,\ d[3]=3,\ d[7]=-3d[1]=2, d[5]=−2, d[3]=3, d[7]=−3，即
 * <p>
 * d=[0,2,0,3,0,−2,0,−3,⋯ ]d = [0, 2, 0, 3, 0, -2, 0, -3, \cdots]
 * d=[0,2,0,3,0,−2,0,−3,⋯]
 * 从左到右累加，得到
 * <p>
 * a=[0,2,2,5,5,3,3,0,⋯ ]a = [0, 2, 2, 5, 5, 3, 3, 0,\cdots]
 * a=[0,2,2,5,5,3,3,0,⋯]
 * capacity=4\textit{capacity}=4capacity=4，由于 max⁡(a)=5>4\max(a)=5>4max(a)=5>4，所以返回 false。
 * <p>
 * 实现方法
 * 有两种写法：
 * <p>
 * 第一种写法是，创建一个长为 100110011001 的差分数组，这可以保证 ddd 数组不会下标越界。
 * 第二种写法是，用平衡树（C++ 中的 map，Java 中的 TreeMap）代替差分数组，因为我们只需要考虑在 fromi\textit{from}_ifrom
 * i
 * ​
 * 和 toi\textit{to}_ito
 * i
 * ​
 * 这些位置上的乘客数，其余位置的乘客是保持不变的，无需考虑。平衡树可以保证我们是从小到大遍历这些位置的。当然，如果你不想用平衡树的话，也可以用哈希表，把哈希表的 key 取出来排序，就可以从小到大遍历这些位置了。
 * 代码实现时，其实无需创建数组 aaa，只需要用一个变量 sss 累加差分值，如果在累加过程中发现 s>capacitys>\textit{capacity}s>capacity 就返回 false。如果没有出现这种情况，就返回 true。
 */
public class CarPooling1094 {

    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[capacity];

        for (int[] tt : trips) {

            int i = tt[1];
            int j = tt[2];
            int val = tt[0];

            diff[i] += val;
            if (j + 1 < diff.length) {
                diff[j + 1] -= val;
            }
        }
        int num = 0;
        //diff是差分，count[i]表示车行驶到位置i时车上的人数，因为count[k] = diff[0]+diff[1]+diff[2]...diff[k]
        //我们需要判断是否所有count[i]都不超过 capacity，于是就得出下面的判断
        for (int x : diff) {
            num += x;
            if (num > capacity) {
                return false;
            }
        }
        return true;

    }
}
